package Algorithm.SlidingWindow;

import java.util.Map;
import java.util.TreeMap;

public class Leetcode846_一手顺子 {
    class Solution {
        public boolean isNStraightHand(int[] hand, int groupSize) {
            if(hand.length % groupSize != 0){
                return false;
            }
            if(groupSize == 1){
                return true;
            }

            TreeMap<Integer, Integer> map = new TreeMap();
            for(int i = 0; i < hand.length; i++){
                map.put(hand[i], map.getOrDefault(hand[i], 0) + 1);
            }

            int[] nums = new int[map.size()];

            int i = 0;
            //处理成排好序的不重复出现数字的数组
            for(Map.Entry<Integer, Integer> entry : map.entrySet()){
                nums[i] = entry.getKey();
                i++;
            }

            i = 0;

            for(int j = 0; j < nums.length; j++){
                if(i==j){
                    continue;
                }

                // j 开始往右滑动，要保证窗口内的数字是连续的
                if(nums[j]-nums[j-1] != 1){
                    return false;
                }

                //同时后面的数字的个数要大于等于前面的数字的个数
                if(map.get(nums[j]) < map.get(nums[j-1])){
                    return false;
                }

                //如果窗口的大小为 group，要把窗口内的数字的个数都减去第一个数字的个数
                if(j - i + 1 < groupSize){
                    continue;
                }else if(j - i + 1 == groupSize){
                    int delta = map.get(nums[i]);
                    for(int k = i; k <= j; k++){
                        map.put(nums[k], map.getOrDefault(nums[k], 0) - delta);
                    }

                    while(i <= j){
                        if(map.getOrDefault(nums[i], 0) < 1){
                            i++;
                        }else{
                            break;
                        }
                    }
                }
            }

            if(map.get(nums[nums.length-1]) > 0 ){
                return false;
            }

            return true;
        }
    }
}
